СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМ 

Алехина Марина Анатольевна, доктор физико-математических наук, профессор, заведующая кафедрой дискретной математики, Пензенский государственный университет, alehina@pnzgu.ru
Васин Алексей Валерьевич, аспирант, Пензенский государственный университет, dm@pnzgu.ru

519.718+004.312

Рассматривается задача синтеза асимптотически оптимальных по надежности схем, реализующих булевы функции, при инверсных неисправностях на выходах элементов в некоторых полных неприводимых базисах из двухвходовых функциональных элементов. Доказано, что в рассматриваемых базисах все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, причем почти для всех функций эти схемы функционируют с ненадежностью, асимптотически равной 2ε при ε→0 (ε – вероятность инверсной неисправности на выходе базисного элемента). Сложность этих схем асимптотически не больше чем в три раза превышает сложность минимальных схем, построенных из абсолютно надежных элементов 

Ключевые слова

надежные схемы, ненадежные элементы, инверсные неисправности, синтез схем, булевы функции

 Скачать статью в формате PDF

1. Neuman von J. Probabilistic logics and the synthesis of reliable organisms from unreliable components / J. von Neuman // Automata studies / ed. by C. Shannon, Mc. Carthy J. – Princeton : Princeton University Press, 1956. – (Русский перевод: Автоматы. – М. : ИЛ, 1956. – С. 68–139).
2. Ортюков, С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов / С. И. Ортюков // Труды семинара по дискретной математике и ее приложениям (Москва, 27–29 января 1987 г.). – М. : Изд-во Моск. ун-та, 1989. – С. 166–168.
3. Uhlig, D. Reliable networks from unreliable gates with almost minimal comlexity / D. Uhlig // Fundamentals of Computation Theory. Intern. сonf. FCT'87 (Kazan, June 1987). Proc. – Berlin : Springer-Verl., 1987. – P. 462–469. – (Lecture Notes in Comput. Sci.; V. 278).
4. Лупанов, О. Б. Об одном методе синтеза схем / О. Б. Лупанов // Известия вузов. Радиофизика. – 1958. – Т. 1. – № 1. – С. 120–140.
5. Алехина, М. А. О надежности и сложности схем в базисе {xy} при инверсных неисправностях элементов / М. А. Алехина // Дискретный анализ и исследование операций. – Новосибирск : Изд-во института математики. – 2005. – Апрель– июнь. – Т. 12. – № 2. – C. 3–11. – (Серия 1).
6. Алехина, М. А. Верхние оценки ненадежности схем в некоторых базисах при инверсных неисправностях на выходах элементов / М. А. Алехина, А. В. Шилов // Известия высших учебных заведений. Поволжский регион. – 2006. – № 5(26). – С. 4–12. – (Естественные науки).
7. Алехина, М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов : монография / М. А. Алехина. – Пенза : Информационно-издательский центр ПензГУ, 2006.